Merkle tree

マークル ツリーの最も一般的で単純な形式はバイナリ メクル ツリーで、バケットは常に 2 つの隣接するチャンクまたはハッシュで構成されます。次のように表すことができます。

各bucketにはいくつかのchankを含め、各bucketのハッシュをとって同じ処理を繰り返し、残りのハッシュの総数が1つになるまで繰り返す

これでできた1つのハッシュをルートハッシュという

最もシンプルなものはBinary Mekle treeというものでbucketは常に2つの隣接するchankまたはハッシュで構成される

https://scrapbox.io/files/63a2e9adb36a4f001d0f0c8e.png

このMekle treeという仕組みを利用するのはMerkle proofという検証方法を利用できるためである

Merkle proofはchank、root hash、chankからrootまでになるbranchで構成されている

証明を行う人はそのbranchのハッシュがツリーの先まで一貫していること、つまり与えられたchankが実際にツリーのその位置にあることを検証できる

BitcoinのMekle tree

ライトクライアントによって全てのトランザクションと全てのブロックをする代わりにブロックヘッダーのみを取得する

直前のブロックヘッダーのハッシュ値

タイムスタンプ

nonce

difficulty

そのブロックのトランザクションを含むMekle treeのルート

もし、ライトクライアントがトランザクションのステータスを判断したい場合、特定のトランザクションがチェーンのブロックヘッダーにあるMekle treeのいずれかにあることを示すMerkle proofを要求するだけで済む

限界

トランザクションを含んでいることは証明できるが、現在のstate(保有状況など)については証明することができない

EthereumではMerkle Treeを派生させたコンセプトを採用している

参考文献